package ljl.alg.jianzhioffer.round3.medium;

public class _66_constructArr {

    /**
     * 如果是我，我会搞两个数组：第一个，前半边；第二个，后半边。最后，循环一遍，对应的值襄城，没问题
     * 注：我这个是抄的路飞。我那个想法有些愚蠢，不写了就。其实是原书作者的想法。
     * */
    public int[] constructArr(int[] a) {
        int[] b = new int[a.length];
        if (a.length == 0) return b;
        b[0] = 1;
        for (int i = 1; i < a.length; i++) {
            b[i] = b[i - 1] * a[i - 1];
        }
        int t = 1;
        for (int i = a.length - 2; i >= 0 ; i--) {
            t *= a[i + 1];
            b[i] *= t;
        }
        return b;
    }

    /**
     * 路飞技高一筹。他用了一个数组 + 一个变量，数组是为了拿到旧值。变量只需要新值，所以不需要数组。
     * */
    class lufei {
        public int[] constructArr(int[] a) {
            int len = a.length;
            if(len == 0) return new int[0];
            int[] b = new int[len];
            b[0] = 1;
            int tmp = 1;
            for(int i = 1; i < len; i++) {
                b[i] = b[i - 1] * a[i - 1];
            }
            for(int i = len - 2; i >= 0; i--) {
                tmp *= a[i + 1];
                b[i] *= tmp;
            }
            return b;
        }
    }

}
